package other.背包问题;

/**
 * 零一背包就是当前项 选与不选 的问题
 * 创建时间：2024-03-27 09:49
 */
public class 零一背包 {
    private int[] w, v;

    /**
     * 0-1背包的方法
     * @param capacity 背包容量
     * @param w 物品体积 w[i] 第i个物品的体积
     * @param v 物品价值 v[i] 第i个物品的价值
     * @return 所选物品不超过capacity容量的情况下，所选物品的最大价值和
     * 枚举第i个物品：
     *     选：剩余容量不变
     *   不选：剩余容量减 w[i]
     * dfs(i, c) = max(dfs(i, c), dfs(i, c - w[i]) + v[i])
     */
    public int zeroOne(int capacity, int[] w, int[] v) {
        this.w = w;
        this.v = v;
        return zeroOneDfs(w.length - 1, capacity);
    }

    public int zeroOneDfs(int i, int r) {
        if (i < 0) {
            return 0;
        }
        if (r < w[i]) {
            zeroOneDfs(i - 1, r);
        }
        int res = Math.max(zeroOneDfs(i - 1, r), zeroOneDfs(i - 1, r - w[i]) + v[i]);
        return res;
    }
}
